//给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 
//
// 测试用例的答案是一个 32-位 整数。 
//
// 子数组 是数组的连续子序列。 
//
// 
//
// 示例 1: 
//
// 
//输入: nums = [2,3,-2,4]
//输出: 6
//解释: 子数组 [2,3] 有最大乘积 6。
// 
//
// 示例 2: 
//
// 
//输入: nums = [-2,0,-1]
//输出: 0
//解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。 
//
// 
//
// 提示: 
//
// 
// 1 <= nums.length <= 2 * 104 
// -10 <= nums[i] <= 10 
// nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数 
// 
// Related Topics 数组 动态规划 
// 👍 1486 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution152 {
    /**
     * 解题思路
     * 1.乘积如果是负数，则最大值会变成最小值
     * 因此记录最大值和最小值，当当前元素是负值时，交换最大值和最小值的数据
     *
     * 解答成功:
     * 			执行耗时:1 ms,击败了96.61% 的Java用户
     * 			内存消耗:41.6 MB,击败了6.99% 的Java用户
     * @param nums
     * @return
     */
    public int maxProduct(int[] nums) {
        int max = Integer.MIN_VALUE, imax=1, imin=1;
        for (int num : nums) {
            if(num < 0) {
                int tmp = imax;
                imax = imin;
                imin = tmp;
            }
            imax = Math.max(imax*num, num);
            imin = Math.min(imin*num, num);
            max = Math.max(imax, max);
        }

        return max;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
